考纲
- 线性表的基本概念
- 线性表的实现，顺序存储，链式存储
- 线性表的应用
知识框架
tips
线性表是一种逻辑结构，表示元素之间一对一的相邻关系。顺序表和链表是指存储结构，两者属于不同层面的概念，因此不要将其混淆。
线性表的基本操作
ADT List{
数据对象:D={ai|ai∈ElemSet,i=1,2,...,n,n>=0}
数据关系:R={<ai-1,ai>|ai-1,ai∈D,i=2,...,n} //i和i-1均为下标
基本操作:
InitList(&L):构建一个空的线性表L
DestroyList(&L):销毁线性表L
ClearList(&L):将线性表重置为空表
ListEmpty(L):若L为空表，返回true，否则返回false
ListLength(L):返回L中数据元素个数
GetElem(L,i,&e):用e返回L中第i个数据元素的值
LocateElem(L,e):返回L中第1个值与e相同的元素在L中的位置。若不存在返回0
PriorElem(L,cur_e,&pre_e):若cur_e是L的数据元素，且不是第一个，则用pre_e返回其前驱，否则操作失败，pre_e无定义
NextElem(L,cur_e,&next_e):若cur_e是L的数据元素，且不是最后一个，则用next_e返回其后继，否则操作失败，next_e无定义
ListInsert(&L,i,e):在L中第i个位置之前插入新的数据元素e，L的长度加1
TraverseList(L):对线性表L进行遍历，在遍历过程中对L的每个结点访问一次。
}
线性表的顺序表示
顺序表的定义
线性表的顺序存储又称顺序表顺序表。
#define MAXSIZE 100 //顺序表可能达到的最大长度
typedef struct{
ElemType *elem; //存储空间基地址
int length; //当前长度
}SqList;
顺序表基本操作实现
此处为严蔚敏版本
初始化
Status InitList(SqList &L){
L.elem = new ElemType[MAXSIZE];
if(!L.elem) exit(OVERFLOW);
L.length = 0;
return OK;
}
tips
C语言:
L.elem= (ElemType*)malloc(sizeof(ElemType)*MAXSIZE);
取值
Status GetElem(SqList L,int i,ElemType &e){
if(i<1||i>L.length) return ERROR;
e=L.elem[i-1];
return OK;
}
时间复杂度:O(1)
查找
int LocateElem(SqList L,int i,ElemType e){
for(i=0;i<L.length();i++) if(L.elem[i]==e) return i+1;
return 0;
}
时间复杂度:O(n)
插入
Status ListInsert(SqList &L,int i,ElemType e){
if((i<1)||(i>L.length+1)) return ERROR;
if(L.length==MAXSIZE) return ERROR;
for(j=L.length-1;j>=i-1;j--) L.elem[j+1]=L.elem[j];
L.elem[i-1]=e;
++L.length;
return OK;
}
时间复杂度:O(n)
删除
Status ListDelete(SqList &L,int i){
if((i<1)||(i>L.length+1)) return ERROR;
for(j=i;j<=L.length-1;j++) L.elemj[j-1]=L.elem[j];
L.elem[i-1]=e;
--L.length;
return OK;
}
时间复杂度:O(n)
线性表的链式表示和实现
单链表的定义和表示
typedef struct LNode{
ElemType data;
struct LNode *next;
}LNode,*LinkList;
tips
一般情况下，为了处理方便，在单链表的第一个结点之前附设一个结点，称之为头结点。图2.8所示的单链表增加头结点后如图2.9所示。
图2.8
图2.9
头结点的单链表的逻辑状态下面对首元结点、头结点、头指针三个容易混淆的概念加以说明。
（1）首元结点是指链表中存储第一个数据元素a1的结点。如图2.8或图2.9所示的结点“ZHAO”。
（2）头结点是在首元结点之前附设的一个结点，其指针域指向首元结点。头结点的数据域可以不存储任何信息，也可存储与数据元素类型相同的其他附加信息。例如，当数据元素为整数型时，头结点的数据域中可存放该线性表的长度。
（3）头指针是指向链表中第一个结点的指针。若链表设有头结点，则头指针所指结点为线性表的头结点；若链表不设头结点，则头指针所指结点为该线性表的首元结点。
链表增加头结点的作用如下
（1）便于首元结点的处理增加了头结点后，首元结点的地址保存在头结点(即其“前驱”结点)的指针域中，则对链表的第一个数据元素的操作与其他数据元素相同，无需进行特殊处理。
（2）便于空表和非空表的统一处理当链表不设头结点时，假设L为单链表的头指针，它应该指向首元结点，则当单链表为长度n为0的空表时，L指针为空（判定空表的条件可记为：L==NULL）。
初始化
Status InitList(LinkList &L)
{//构造一个空的单链表L
L=new LNode; //生成新结点作为头结点，用头指针L指向头结点
L->next=NULL; //头结点的指针域置空
return OK;
}
tips：算法步骤
① 生成新结点作为头结点，用头指针L指向头结点。
② 头结点的指针域置空。
取值
tips：算法步骤
① 用指针p指向首元结点，用j做计数器初值赋为1。
② 从首元结点开始依次顺着链域next向下访问，只要指向当前结点的指针p不为空（NULL），并且没有到达序号为i的结点，则循环执行以下操作：·p指向下一个结点；·计数器j相应加1。
③ 退出循环时，如果指针p为空，或者计数器j大于i，说明指定的序号i值不合法（i大于表长n或i小于等于0），取值失败返回ERROR；否则取值成功，此时j=i时，p所指的结点就是要找的第i个结点，用参数e保存当前结点的数据域，返回OK。
Status GetElem(LinkList L,int i,ElemType &e)
{//在带头结点的单链表L中根据序号i获取元素的值，用e返回L中第i个数据元素的值
p=L->next;j=1; //初始化，p指向首元结点，计数器j初值赋为1
while(p&&j<i) //顺链域向后扫描，直到p为空或p指向第i个元素
{
p=p->next; //p指向下一个结点
++j; //计数器j相应加1
}
if(!p||j>i)return ERROR; //i值不合法i>n或i≤0
e=p->data; //取第i个结点的数据域
return OK;
}
时间复杂度为O(n)。
查找
tips：算法步骤
① 用指针p指向首元结点。
② 从首元结点开始依次顺着链域next向下查找，只要指向当前结点的指针p不为空，并且p所指结点的数据域不等于给定值e，则循环执行以下操作：p指向下一个结点。
③ 返回p。若查找成功，p此时即为结点的地址值，若查找失败，p的值即为NULL。
LNode *LocateElem(LinkList L，ElemType e)
{//在带头结点的单链表L中查找值为e的元素
p=L->next; //初始化，p指向首元结点
while(p && p->data!=e) //顺链域向后扫描，直到p为空或p所指结点的数据域等于e
p=p->next; //p指向下一个结点
return p; //查找成功返回值为e的结点地址p，查找失败p为NULL
}
时间复杂度：O(n)。
插入
tips：算法步骤
① 查找结点ai−1并由指针p指向该结点。
② 生成一个新结点*s。
③ 将新结点*s的数据域置为e。
④ 将新结点*s的指针域指向结点ai。
⑤ 将结点*p的指针域指向新结点*s。
Status ListInsert(LinkList &L,int i,ElemType e)
{//在带头结点的单链表L中第i个位置插入值为e的新结点
p=L;j=0;
while(p && (j<i−1))
{p=p->next;++j;} //查找第i−1个结点，p指向该结点
if(!p||j>i−1) return ERROR; //i>n+1或者i<1
s=new LNode; //生成新结点*s
s->data=e; //将结点*s的数据域置为e
s->next=p->next; //将结点*s的指针域指向结点ai
p->next=s; //将结点*p的指针域指向结点*s
return OK;
}
时间复杂度：O(n)。
删除
tips：算法步骤
① 查找结点ai−1并由指针p指向该结点。
② 临时保存待删除结点ai的地址在q中，以备释放。
③ 将结点*p的指针域指向ai的直接后继结点。
④ 释放结点ai的空间。
Status ListDelete(LinkList &L,int i)
{//在带头结点的单链表L中，删除第i个元素
p=L;j=0;
while((p->next) && (j<i-1)) //查找第i−1个结点，p指向该结点
{p=p->next;++j;}
if(!(p->next)||(j>i-1)) return ERROR; //当i>n或i<1时，删除位置不合理
q=p->next; //临时保存被删结点的地址以备释放
p->next=q->next; //改变删除结点前驱结点的指针域
delete q; //释放删除结点的空间
return OK;
}
tips：说明
删除算法中的循环条件(p->next&&j
时间复杂度：O(n)。
创建单链表
前插法创建单链表
tips：算法步骤
① 创建一个只有头结点的空链表。
② 根据待创建链表包括的元素个数n，循环n次执行以下操作：
·生成一个新结点*p；
·输入元素值赋给新结点*p的数据域；
·将新结点*p插入到头结点之后。
void CreateList_H(LinkList &L,int n)
{//逆位序输入n个元素的值，建立带表头结点的单链表L
L=new LNode;
L->next=NULL; //先建立一个带头结点的空链表
for(i=0;i<n;++i)
{
p=new LNode; //生成新结点*p
cin>>p->data; //输入元素值赋给新结点*p的数据域
p->next=L->next;L->next=p; //将新结点*p插入到头结点之后
}
}
时间复杂度：O(n)。
后插法创建单链表
tips：算法步骤
① 创建一个只有头结点的空链表。
② 尾指针r初始化，指向头结点。
③ 根据创建链表包括的元素个数n，循环n次执行以下操作：
·生成一个新结点*p；
·输入元素值赋给新结点*p的数据域；
·将新结点*p插入到尾结点*r之后；
·尾指针r指向新的尾结点*p。
void CreateList_R(LinkList &L,int n)
{//正位序输入n个元素的值，建立带表头结点的单链表L
L=new LNode;
L->next=NULL; //先建立一个带头结点的空链表
r=L; //尾指针r指向头结点
for(i=0;i<n;++i)
{
p=new LNode; //生成新结点
cin>>p->data; //输入元素值赋给新结点*p的数据域
p->next=NULL; r->next=p; //将新结点*p插入尾结点*r之后
r=p; //r指向新的尾结点*p
}
}
时间复杂度：O(n)。
循环链表
特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。
双向链表
//- - - - - 双向链表的存储结构- - - - -
typedef struct DuLNode
{
ElemType data; //数据域
struct DuLNode *prior; //指向直接前驱
struct DuLNode *next; //指向直接后继
}DuLNode,*DuLinkList;
双向链表的插入和删除
tips：图
图2.20
图2.21
插入
Status ListInsert_DuL(DuLinkList &L,int i,ElemType e)
{//在带头结点的双向链表L中第i个位置之前插入元素e
if(!(p=GetElem_DuL(L,i))) //在L中确定第i个元素的位置指针p
return ERROR; //p为NULL时，第i个元素不存在
s=new DuLNode; //生成新结点*s
s->data=e; //将结点*s数据域置为e
s->prior=p->prior; //将结点*s插入L中，此步对应图2.20①
p->prior->next=s; //对应图2.20②
s->next=p; //对应图2.20③
p->prior=s; //对应图2.20④
return OK;
}
删除
Status ListDelete_DuL(DuLinkList &L,int i)
{//删除带头结点的双向链表L中的第i个元素
if(!(p=GetElem_DuL(L,i))) //在L中确定第i个元素的位置指针p
return ERROR; //p为NULL时，第i个元素不存在
p->prior->next=p->next; //修改被删结点的前驱结点的后继指针，对应图2.21①
p->next->prior=p->prior; //修改被删结点的后继结点的前驱指针，对应图2.21②
delete p; //释放被删结点的空间
return OK;
}
时间复杂度：O(n)。
顺序表和链表的比较
空间性能的比较
时间性能的比较
- 存取元素的效率存取元素的效率
- 插入和删除操作的效率插入和删除操作的效率
线性表的应用
线性表的合并
【问题描述】已知两个集合A和B，现要求一个新的集合A=AUB。
例如，设A=(7，5，3，11) B=(2，6，3)
合并后A=(7，5，3，11，2，6)
tips：算法步骤
① 分别获取LA表长m和LB表长n。
② 从LB中第1个数据元素开始，循环n次执行以下操作：
·从LB中查找第i（1≤i≤n）个数据元素赋给e；
·在LA中查找元素e，如果不存在，则将e插在表LA的最后。
void MergeList(List &LA,List LB)
{//将所有在线性表LB中但不在LA中的数据元素插入到LA中
m=ListLength(LA); n=ListLength(LB); //求线性表的长度
for(i=1;i<=n;i++)
{
GetElem(LB,i,e); //取LB中第i个数据元素赋给e
if(!LocateElem(LA,e)) //LA中不存在和e相同的数据元素
ListInsert(LA,++m,e); //将e插在LA的最后
}
}
时间复杂度：O(m×n)
有序表有序表的合并
顺序有序表的合并
【问题描述】
有序集合是指集合中的元素有序排列。已知两个有序集合A和B，数据元素按值非递减有序排列，现要求一个新的集合C=AUB，使集合C中的数据元素仍按值非递减有序排列。
例如，设A=(3, 5, 8, 11) B=(2, 6, 8, 9, 11, 15, 20)
则C=(2, 3, 5, 6, 8, 8, 9, 11, 11, 15, 20)
tips：算法步骤
① 创建一个表长为m+n的空表LC。
② 指针pc初始化，指向LC的第一个元素。
③ 指针pa和pb初始化，分别指向LA和LB的第一个元素。
④ 当指针pa和pb均未到达相应表尾时，则依次比较pa和pb所指向的元素值，从LA或LB中“摘取”元素值较小的结点插入到LC的最后。
⑤ 如果pb已到达LB的表尾，依次将LA的剩余元素插入LC的最后。
⑥ 如果pa已到达LA的表尾，依次将LB的剩余元素插入LC的最后。
void MergeList_Sq(SqList LA,SqList LB,SqList &LC)
{//已知顺序有序表LA和LB的元素按值非递减排列
//归并LA和LB得到新的顺序有序表LC，LC的元素也按值非递减排列
LC.length=LA.length+LB.length; //新表长度为待合并两表的长度之和
LC.elem=new ElemType[LC.length]; //为合并后的新表分配一个数组空间
pc=LC.elem; //指针pc指向新表的第一个元素
pa=LA.elem; pb=LB.elem; //指针pa和pb的初值分别指向两个表的第一个元素
pa_last=LA.elem+LA.length-1; //指针pa_last指向LA的最后一个元素
pb_last=LB.elem+LB.length-1; //指针pb_last指向LB的最后一个元素
while((pa<=pa_last)&&(pb<=pb_last)) //LA和LB均未到达表尾
{
if(*pa<=*pb) *pc++=*pa++; //依次“摘取”两表中值较小的结点插入到LC的最后
else *pc++=*pb++;
}
while(pa<=pa_last) *pc++=*pa++; //LB已到达表尾，依次将LA的剩余元素插入LC的最后
while(pb<=pb_last) *pc++=*pb++; //LA已到达表尾，依次将LB的剩余元素插入LC的最后
}
时间复杂度为O(m+n)。 空间复杂度也为O(m+n)，空间复杂度较高。
链式有序表的合并
tips：算法步骤
① 指针pa和pb初始化，分别指向LA和LB的第一个结点。
② LC的结点取值为LA的头结点。
③ 指针pc初始化，指向LC的头结点。
④ 当指针pa和pb均未到达相应表尾时，则依次比较pa和pb所指向的元素值，从LA或LB中“摘取”元素值较小的结点插入到LC的最后。
⑤ 将非空表的剩余段插入到pc所指结点之后。
⑥ 释放LB的头结点。
void MergeList_L(LinkList &LA,LinkList &LB,LinkList &LC)
{//已知单链表LA和LB的元素按值非递减排列
//归并LA和LB得到新的单链表LC，LC的元素也按值非递减排列
pa=LA->next;pb=LB->next; //pa和pb的初值分别指向两个表的第一个结点
LC=LA; //用LA的头结点作为LC的头结点
pc=LC; //pc的初值指向LC的头结点
while(pa&&pb)
{//LA和LB均未到达表尾，依次“摘取”两表中值较小的结点插入到LC的最后
if(pa->data<=pb->data) //“摘取”pa所指结点
{
pc->next=pa; //将pa所指结点链接到pc所指结点之后
pc=pa; //pc指向pa
pa=pa->next; //pa指向下一结点
}
else //“摘取”pb所指结点
{
pc->next=pb; //将pb所指结点链接到pc所指结点之后
pc=pb; //pc指向pb
pb=pb->next; //pb指向下一结点
}
} //while
pc->next=pa?pa:pb; //将非空表的剩余段插入到pc所指结点之后
delete LB; //释放LB的头结点
}
时间复杂度为O(m+n)。 空间复杂度也为O(1)。
案例分析与实现
案例2.1：一元多项式的运算。
【案例分析】一元多项式可以抽象成一个线性表。在计算机中，我们可以采用数组来表示一元多项式的线性表。
利用数组p表示：数组中每个分量p[i]表示多项式每项的系数pi，数组分量的下标i即对应每项的指数。数组中非零的分量个数即为多项式的项数。
例如，多项式P(x)=10+5x−4x2+3x3+2x4可以用表2.1所示的数组表示。
表2.1 多项式的数组表示
显然，利用上述方法表示一元多项式，多项式相加的算法很容易实现，只要把两个数组对应的分量项相加就可以了。
案例2.2：稀疏多项式的运算。
tips：【案例分析】
由2.2节的讨论我们已知，稀疏多项式也可以抽象成一个线性表。结合2.7节介绍的两个有序表的归并方法，可以看出，稀疏多项式的相加过程和归并两个有序表的过程极其类似，不同之处仅在于，后者在比较数据元素时只出现两种情况（小于等于、大于），而多项式的相加过程在比较两个多项式指数时要考虑三种情况（等于、小于、大于）。因此，多项式相加的过程可以根据算法2.16和算法2.17改进而成。
和顺序存储结构相比，利用链式存储结构更加灵活，更适合表示一般的多项式，合并过程的空间复杂度为O(1)，所以较为常用。本节将给出如何利用单链表的基本操作来实现多项式的相加运算。
例如，图2.22所示两个链表分别表示多项式A(x)=7+3x+9x8+5x17和多项式B(x)=8x+22x7−9x8。从图中可见，每个结点表示多项式中的一项。
如何实现用这种单链表表示的多项式的加法运算呢？
根据多项式相加的运算规则：对于两个多项式中所有指数相同的项，对应系数相加，若其和不为零，则作为“和多项式”中的一项插入到“和多项式”链表中去；对于两个多项式中指数不相同的项，则将指数值较小的项插入到“和多项式”链表中去。“和多项式”链表中的结点无需生成，而应该从两个多项式的链表中摘取。图2.22所示的两个多项式相加的结果如图2.23所示，图中的长方框表示已被释放的结点。
【案例实现】
数据结构定义为：
typedef struct PNode
{
float coef; //系数
int expn; //指数
struct PNode *next; //指针域
}PNode,*Polynomial;
多项式的创建
tips：【算法步骤】
① 创建一个只有头结点的空链表。
② 根据多项式的项的个数n，循环n次执行以下操作：
·生成一个新结点*s；
·输入多项式当前项的系数和指数赋给新结点*s的数据域；
·设置一前驱指针pre，用于指向待找到的第一个大于输入项指数的结点的前驱，pre初值指向头结点；
·指针q初始化，指向首元结点；
·循链向下逐个比较链表中当前结点与输入项指数，找到第一个大于输入项指数的结点*q；
·将输入项结点*s插入到结点*q之前。
void CreatePolyn(Polynomial &P,int n)
{//输入n项的系数和指数，建立表示多项式的有序链表P
P=new PNode;
P->next=NULL; //先建立一个带头结点的单链表
for(i=1;i<=n;++i) //依次输入n个非零项
{
s=new PNode; //生成新结点
cin>>s->coef>>s->expn; //输入系数和指数
pre=P; //pre用于保存q的前驱，初值为头结点
q=P->next; //q初始化，指向首元结点
while(q&&q->expn<s->expn) //通过比较指数找到第一个大于输入项指数的项*q
{
pre=q;
q=q->next;
} //while
s->next=q; //将输入项s插入到q和其前驱结点pre之间
pre->next=s;
} //for
}
时间复杂度为O(n2)。
多项式的相加
创建两个多项式链表后，便可以进行多项式的加法运算了。假设头指针为Pa和Pb的单链表分别为多项式A和B的存储结构，指针p1和p2分别指向A和B中当前进行比较的某个结点，则逐一比较两个结点中的指数项，对于指数相同的项，对应系数相加，若其和不为零，则将插入到“和多项式”链表中去；对于指数不相同的项，则通过比较将指数值较小的项插入到“和多项式”链表中去。
tips：【算法步骤】
① 指针p1和p2初始化，分别指向Pa和Pb的首元结点。
② p3指向和多项式的当前结点，初值为Pa的头结点。
③ 当指针p1和p2均未到达相应表尾时，则循环比较p1和p2所指结点对应的指数值（p1->expn与p2->expn），有下列3种情况：·当p1->expn等于p2->expn时，则将两个结点中的系数相加，若和不为零，则修改p1所指结点的系数值，同时删除p2所指结点，若和为零，则删除p1和p2所指结点；
·当p1->expn小于p2->expn时，则应摘取p1所指结点插入到“和多项式”链表中去；
·当p1->expn大于p2->expn时，则应摘取p2所指结点插入到“和多项式”链表中去。
④ 将非空多项式的剩余段插入到p3所指结点之后。
⑤ 释放Pb的头结点。
void AddPolyn(Polynomial &Pa,Polynomial &Pb)
{//多项式加法：Pa=Pa+Pb，利用两个多项式的结点构成“和多项式”
p1=Pa->next; p2=Pb->next; //p1和p2初值分别指向Pa和Pb的首元结点
p3=Pa; //p3指向和多项式的当前结点，初值为Pa
while(p1&&p2) //p1和p2均非空
{
if(p1->expn==p2->expn) //指数相等
{
sum=p1->coef+p2->coef; //sum保存两项的系数和
if(sum!=0) //系数和不为0
{
p1->coef=sum; //修改Pa当前结点的系数值为两项系数的和
p3->next=p1; p3=p1; //将修改后的Pa当前结点链在p3之后，p3指向p1
p1=p1->next; //p1指向后一项
r=p2; p2=p2->next; delete r; //删除Pb当前结点，p2指向后一项
}
else //系数和为0
{
r=p1; p1=p1->next; delete r; //删除Pa当前结点，p1指向后一项
r=p2; p2=p2->next; delete r; //删除Pb当前结点，p2指向后一项
}
}
else if(p1->expn<p2->expn) //Pa当前结点的指数值小
{
p3->next=p1; //将p1链在p3之后
p3=p1; //p3指向p1
p1=p1->next; //p1指向后一项
}
else //Pb当前结点的指数值小
{
p3->next=p2; //将p2链在p3之后
p3=p2; //p3指向p2
p2=p2->next; //p2指向后一项
}
} //while
p3->next=p1?p1:p2; //插入非空多项式的剩余段
delete Pb; //释放Pb的头结点
}
时间复杂度为O(m+n)，空间复杂度为O(1)
案例2.3：图书信息管理系统。
tips：【案例分析】
（1）对于查找、插入、删除这3个功能的算法，本章已分别给出了线性表利用顺序存储结构和链式存储结构表示时相应的算法描述。
（2）对于修改功能，可以通过调用查找算法，找到满足条件的图书进行修改即可。
（3）对于排序功能，如果在没有时间复杂度限制的情况下，可以采用读者熟悉的冒泡排序来完成；如果图书数目较多，对排序算法的时间效率要求较高，在学完第8章的内部排序算法后，可以选取一种较高效的排序算法来实现，例如，快速排序。
（4）对于计数功能，如果采取顺序存储结构，线性表的长度是它的属性，可以直接通过返回length的值实现图书个数的统计功能，时间复杂度是O(1)；如果采取链式存储结构，则需要通过从首元结点开始，附设一个计数器进行计数，一直“数”到最后一个结点，时间复杂度是O(n)。
在实现图书信息管理系统时，具体采取哪种存储结构，可以根据实际情况而定。如果图书数据较多，需要频繁地进行插入和删除操作，则宜采取链表表示；反之，如果图书数据个数变化不大，很少进行插入和删除操作，则宜采取顺序表表示。
此案例中所涉及的算法比较基础，但非常重要，读者可以分别采用顺序表和链表实现此案例的相应功能，作为本章内容的实验题目来完成。
小结
- 线性表的逻辑结构特性是指数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构（顺序表）和链式存储结构（链表）。
- 对于顺序表，元素存储的相邻位置反映出其逻辑上的线性关系，可借助数组来表示。给定数组的下标，便可以存取相应的元素，可称为随机存取结构。而对于链表，是依靠指针来反映其线性逻辑关系的，链表结点的存取都要从头指针开始，顺链而行，所以不属于随机存取结构，可称之为顺序存取结构
顺序表和链表的比较
单链表、循环链表和双向链表的比较
习题
（ 1）顺 序表中 第一个 元 素的存储 地址 是 100 ，每 个元素的 长度 为 2，则 第 5 个 元 素 的 地 址 是 （ ）。
A． 110 B ． 108 C． 100 D． 120
tips：答案
B
解释：顺序表中的数据连续存储，所以第 5 个元素的地址为： 100+2*4=108 。
（2）在含n个结点的顺序表中，算法的时间复杂度是O(1)的操作是（ ）。
A. 访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）
B. 在第i个结点后插入一个新结点（1≤i≤n）
C. 删除第i个结点（1≤i≤n）
D. 将n个结点从小到大排序
tips：答案
A
解释： 在顺序表中插入一个结点的时间复杂度都是 O(n2) ，排序的时间复杂度为 O(n2 ) 或 O(nlog2n)。顺序表是一种随机存取结构，访问第 i 个结点和求第 i 个结点的直接前驱都可以直接通过数组的下标直接定位，时间复杂度是 O(1) 。
（3）在一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动的元素个数为（ ）。
A. 8
B. 63.5
C. 63
D. 7
tips：答案
B
解释：平均要移动的元素个数为： n/2 。
（4）链接存储的存储结构所占存储空间（ ）。 A. 分为两部分，一部分存放结点值，另一部分存放表示结点间关系的指针 B. 只有一部分，存放结点值 C. 只有一部分，存储表示结点间关系的指针 D. 分两部分，一部分存放结点值，另一部分存放结点所占单元数
tips：答案
A
（5）线性表若采用链式存储结构，要求内存中可用存储单元的地址（ ）。
A. 必须是连续的
B. 部分地址必须是连续的
C. 一定是不连续的
D. 连续或不连续都可以
tips：答案
D
（6）线性表L在（ ）情况下适用于使用链式结构实现。
A. 需经常修改L中的结点值
B. 需不断对L进行删除、插入
C. L中含有大量的结点
D. L中结点结构复杂
tips：答案
B
解释：链表最大的优点在于插入和删除时不需要移动数据，直接修改指针即可。
（7）单链表的存储密度（ ）。
A. 大于1
B. 等于1
C. 小于1
D. 不能确定
tips：答案
C
解释：存储密度是指一个结点数据本身所占的存储空间和整个结点所占的存储空 间之比，假设单链表一个结点本身所占的空间为 D，指针域所占的空间为 N，则存储密 度为： D/(D+N) ，一定小于 1。
（8）将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是（ ）。
A. n
B. 2n−1
C. 2n
D. n−1
tips：答案
A
解释：当第一个有序表中所有的元素都小于（或大于）第二个表中的元素，只需 要用第二个表中的第一个元素依次与第一个表的元素比较，总计比较 n 次。
（9）在一个长度为n的顺序表中，在第i个元素（1≤i≤n+1）之前插入一个新元素时需向后移动（ ）个元素。
A. n−i
B. n−i+1
C. n−i−1
D. i
tips：答案
B
（10）线性表L=(a1，a2,…，an)，下列陈述正确的是（ ）。
A. 每个元素都有一个直接前驱和一个直接后继
B. 线性表中至少有一个元素
C. 表中诸元素的排列必须是由小到大或由大到小
D. 除第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继
tips：答案
D
（11）创建一个包括n个结点的有序单链表的时间复杂度是（）。
A. O(1)
B. O(n)
C. O(n2)
D. O(nlog2n)
tips：答案
答案： C
解释：单链表创建的时间复杂度是 O(n) ，而要建立一个有序的单链表，则每生成一个新结点时需要和已有的结点进行比较，确定合适的插入位置，所以时间复杂度是O(n2) 。
（12）以下陈述错误的是（ ）。
A. 求表长、定位这两种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低
B. 顺序存储的线性表可以随机存取
C. 由于顺序存储要求连续的存储区域，所以在存储管理上不够灵活
D. 线性表的链式存储结构优于顺序存储结构
tips：答案
答案： D
解释： 链式存储结构和顺序存储结构各有优缺点，有不同的适用场合。
（13）在单链表中，要将s所指结点插入到p所指结点之后，其语句应为（ ）。
A. s->next=p+1; p->next=s;
B. (p).next=s; (s).next=(*p).next;
C. s->next=p->next; p->next=s->next;
D. s->next=p->next; p->next=s;
tips：答案
D
（14）在双向链表存储结构中，删除p所指结点时修改指针的操作为（ ）。
A. p->next->prior=p->prior; p->prior->next=p->next;
B. p->next=p->next->next; p->next->prior=p;
C. p->prior->next=p; p->prior=p->prior->prior;
D. p->prior=p->next->next; p->next=p->prior->prior;
tips：答案
A
（15）在双向循环链表中，在p指针所指的结点后插入q所指向的新结点，其修改指针的操作是（ ）。
A. p->next=q; q->prior=p; p->next->prior=q; q->next=q;
B. p->next=q; p->next->prior=q; q->prior=p; q->next=p->next;
C. q->prior=p; q->next=p->next; p->next->prior=q; p->next=q;
D. q->prior=p; q->next=p->next; p->next=q; p->next->prior=q;
tips：答案
C
2．算法设计题(答案待商议) （1）将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使用原来两个链表的存储空间，不另外占用其他的存储空间。表中不允许有重复的数据。
tips：答案
（ 1）将两个递增的有序链表合并为一个递增的有序链表。 要求结果链表仍使用原来两个 链表的存储空间 , 不另外占用其它的存储空间。表中不允许有重复的数据。
[ 题目分析 ]
合并后的新表使用头指针 Lc 指向， pa 和 pb 分别是链表 La 和 Lb 的工作指针 , 初始化为 相应链表的第一个结点，从第一个结点开始进行比较，当两个链表 La 和 Lb 均为到达表尾结 点时，依次摘取其中较小者重新链接在 Lc 表的最后。如果两个表中的元素相等，只摘取 La 表中的元素，删除 Lb 表中的元素，这样确保合并后表中无重复的元素。当一个表 到达表尾结 点，为空时，将非空表的剩余元素直接链接在 Lc 表的最后。
[ 算法描述 ]
void MergeList(LinkList &La,LinkList &Lb,LinkList &Lc)
{// 合并链表 La 和 Lb，合并后的新表使用头指针 Lc 指向
pa=La->next; pb=Lb->next;
//pa 和 pb 分别是链表 La 和 Lb 的工作指针 , 初始化为相应链表的第一个结点
Lc=pc=La; // 用 La 的头结点作为 Lc 的头结点
while(pa && pb) {
if(pa->datadata)
{pc->next=pa;pc=pa;pa=pa->next;}
// 取较小者 La 中的元素，将 pa 链接在 pc 的后面， pa 指针后移
else if(pa->data>pb->data)
{pc->next=pb; pc=pb; pb=pb->next;}
// 取较小者 Lb 中的元素，将 pb 链接在 pc 的后面， pb 指针后移
else // 相等时取 La 中的元素，删除 Lb 中的元素
{
pc->next=pa;
pc=pa;pa=pa->next;
q=pb->next;
delete pb ;
pb =q;
}
}
pc->next=pa?pa:pb; // 插入剩余段
delete Lb; // 释放 Lb 的头结点
}
（2）将两个非递减的有序链表合并为一个非递增的有序链表。要求结果链表仍使用原来两个链表的存储空间，不另外占用其他的存储空间。表中允许有重复的数据。
tips：答案
[ 题目分析 ]合并后的新表使用头指针 Lc 指向， pa 和 pb 分别是链表 La 和 Lb 的工作指针 , 初始化为 相应链表的第一个结点，从第一个结点开始进行比较，当两个链表 La 和 Lb 均为到达表尾结 点时，依次摘取其中较小者重新链接在 Lc 表的表头结点之后，如果两个表中的元素相等，只 摘取 La 表中的元素，保留 Lb 表中的元素。当一个表到达表尾结点，为空时，将非空表的剩 余元素依次摘取，链接在 Lc 表的表头结点之后。
[ 算法描述 ]
void MergeList(LinkList& La, LinkList& Lb, LinkList& Lc, )
{// 合并链表 La 和 Lb，合并后的新表使用头指针 Lc 指向
pa=La->next; pb=Lb->next;
//pa 和 pb 分别是链表 La 和 Lb 的工作指针 , 初始化为相应链表的第一个结点
Lc=pc=La; // 用 La 的头结点作为 Lc 的头结点
Lc->next=NULL;
while(pa||pb )
{// 只要存在一个非空表，用 q 指向待摘取的元素
if(!pa)
{q=pb; pb=pb->next;}
//La 表为空，用 q 指向 pb ， pb 指针后移
else if(!pb)
{q=pa; pa=pa->next;}
//Lb 表为空，用 q 指向 pa ， pa 指针后移
else if(pa->datadata)
{q=pa; pa=pa->next;}
// 取较小者（包括相等） La 中的元素，用 q 指向 pa， pa 指针后移
else
{q=pb; pb=pb->next;}
// 取较小者 Lb 中的元素，用 q 指向 pb， pb 指针后移
q->next = Lc->next; Lc->next = q;
// 将 q 指向的结点插在 Lc 表的表头结点之后
}
delete Lb; // 释放 Lb 的头结点
}
（3）已知两个链表A和B分别表示两个集合，其元素递增排列。请设计一个算法，用于求出A与B的交集，并存放在A链表中。
tips：答案
[ 题目分析 ]只有同时出现在两集合中的元素才出现在结果表中 , 合并后的新表使用头指针 Lc 指向。 pa 和 pb 分别是链表 La 和 Lb 的工作指针 , 初始化为相应链表的第一个结点， 从第一个结点开 始进行比较，当两个链表 La 和 Lb 均为到达表尾结点时，如果两个表中相等的元素时，摘取 La 表中的元素，删除 Lb 表中的元素；如果其中一个表中的元素较小时，删除此表中较小的 元素，此表的工作指针后移。当链表 La 和 Lb 有一个到达表尾结点，为空时，依次删除另一 个非空表中的所有元素。
void Mix(LinkList& La, LinkList& Lb, LinkList& Lc)
{pa=La->next;pb=Lb->next;
pa 和 pb 分别是链表 La 和 Lb 的工作指针 , 初始化为相应链表的第一个结点
Lc=pc=La; // 用 La 的头结点作为 Lc 的头结点
while(pa&&pb)
{
if(pa->data==pb- >data) ∥交集并入结果表中。
{ pc->next=pa;pc=pa;pa=pa->next;
u=pb;pb=pb->next; delete u;}
else if(pa->datadata)
{u=pa;pa=pa->next; delete u;}
else
{u=pb; pb=pb->next; delete u;}
}
while(pa){u=pa; pa=pa->next; delete u;} ∥ 释放结点空间
while(pb) {u=pb; pb=pb->next; delete u ;} ∥释放结点空间
pc- >next=null; ∥置链表尾标记。
delete Lb; // 释放 Lb 的头结点
}
（4）已知两个链表A和B分别表示两个集合，其元素递增排列。请设计算法求出两个集合A和B的差集（即仅由在A中出现而不在B中出现的元素所构成的集合），并以同样的形式存储，同时返回该集合的元素个数。
tips：答案
[ 题目分析 ]求两个集合 A 和 B 的差集是指在 A 中删除 A 和 B 中共有的元素，即删除链表中的相应结 点 , 所以要保存待删除结点的前驱，使用指针 pre 指向前驱结点。 pa 和 pb 分别是链表 La 和 Lb 的工作指针 , 初始化为相应链表的第一个结点，从第一个结点开始进行比较，当两个链表 La 和 Lb 均为到达表尾结点时，如果 La 表中的元素小于 Lb 表中的元素， pre 置为 La 表的工 作指针 pa 删除 Lb 表中的元素；如果其中一个表中的元素较小时，删除此表中较小的元素， 此表的工作指针后移。 当链表 La 和 Lb 有一个为空时， 依次删除另一个非空表中的所有元素。
void Difference （ LinkList& La, LinkList& Lb,int *n ） { ∥差集的结果存储于单链表 La 中， *n 是结果集合中元素个数，调用时为 0
pa=La->next; pb=Lb->next;
∥ pa 和 pb 分别是链表 La 和 Lb 的工作指针 , 初始化为相应链表的第一个结点
pre=La; ∥ pre 为 La 中 pa 所指结点的前驱结点的指针
while （ pa&&pb）
{
if （ pa->datadata ）
{pre=pa;pa=pa->next;*n++;}
∥ A 链表中当前结点指针后移
else if （ pa->data>q->data ）
q=q->next; ∥ B 链表中当前结点指针后移
else
{
pre->next=pa->next; ∥处理 A， B 中元素值相同的结点，应删除
u=pa; pa=pa->next;delete u;
} ∥删除结点
}
}
（5）设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B和C，其中B表的结点为A表中值小于零的结点，而C表的结点为A表中值大于零的结点（链表A中的元素为非零整数，要求B、C表利用A表的结点）。
tips：答案
[ 题目分析 ]
B 表的头结点使用原来 A 表的头结点，为 C 表新申请一个头结点。从 A 表的第一个结点 开始，依次取其每个结点 p，判断结点 p 的值是否小于 0，利用前插法，将小于 0 的结点插入 B 表 , 大于等于 0 的结点插入 C 表。
[ 算法描述 ]
void DisCompose(LinkedList A)
{
B=A;
B->next= NULL; ∥ B 表初始化
C=new LNode;∥为 C 申请结点空间
C->next=NULL; ∥ C 初始化为空表
p=A->next; ∥ p 为工作指针
while(p!= NULL)
{
r=p->next; ∥暂存 p 的后继
if(p->datanext=B->next; B- >next=p; } ∥将小于 0 的结点链入 B 表 , 前插法
else
{p->next=C->next; C- >next=p; }∥将大于等于 0 的结点链入 C 表 , 前插法
p=r; ∥p 指向新的待处理结点。
}
}
（6）设计一个算法，通过一趟遍历确定长度为n的单链表中值最大的结点。
tips：答案
[ 题目分析 ]假定第一个结点中数据具有最大值，依次与下一个元素比较，若其小于下一个元素，则 设其下一个元素为最大值，反复进行比较，直到遍历完该链表。
[ 算法描述 ]
ElemType Max (LinkList L ){
if(L->next==NULL) return NULL;
pmax=L->next; // 假定第一个结点中数据具有最大值
p=L->next->next;
while(p != NULL ){// 如果下一个结点存在
if(p->data > pmax->data) pmax=p;// 如果 p 的值大于 pmax 的值，则重新赋值
p=p->next;// 遍历链表
}
return pmax->data;
}
（7）设计一个算法，将链表中所有结点的链接方向“原地”逆转，即要求仅利用原表的存储空间，换句话说，要求算法的空间复杂度为O(1)。
tips：答案
[ 题目分析 ]从首元结点开始，逐个地把链表 L 的当前结点 p 插入新的链表头部。
[ 算法描述 ]
void inverse(LinkList &L)
{// 逆置带头结点的单链表 L
p=L->next; L->next=NULL;
while ( p) {
q=p->next; // q 指向 *p 的后继
p->next=L->next;
L->next=p; // *p 插入在头结点之后
p = q;
}
}
（ 8）设计一个算法，删除递增有序链表中值大于 mink 且小于 maxk 的所有元素（ mink
和 maxk 是给定的两个参数，其值可以和表中的元素相同，也可以不同 ）。
tips：答案
[ 题目分析 ]分别查找第一个值 >mink 的结点和第一个值 ≥ maxk 的结点，再修改指针，删除值大于 mink 且小于 maxk 的所有元素。
[ 算法描述 ]
void delete(LinkList &L, int mink, int maxk) {
p=L->next; // 首元结点
while (p && p->datanext; } // 查找第一个值 >mink 的结点
if (p) {
while (p && p->datanext;
// 查找第一个值 ≥ maxk 的结点
q=pre->next; pre->next=p; // 修改指针
while (q!=p) {
s=q->next; delete q; q=s;
} // 释放结点空间
}//if
}
（9）已知p指向双向循环链表中的一个结点，其结点结构为data、prior、next三个域，写出算法change(p)，交换p所指向的结点及其前驱结点的顺序。
tips：答案
[ 题目分析 ]知道双向循环链表中的一个结点，与前驱交换涉及到四个结点（ p 结点，前驱结点，前 驱的前驱结点，后继结点）六条链。
[ 算法描述 ]
void Exchange （ LinkedList p ） // p 是双向循环链表中的一个结点，本算法将 p 所指结点与其前驱结点交换。
{ q=p->llink ；
q->llink->rlink=p ；// p 的前驱的前驱之后继为 p
p->llink=q->llink ；// p 的前驱指向其前驱的前驱。
q->rlink=p->rlink ；// p 的前驱的后继为 p 的后继。
q->llink=p ；// p 与其前驱交换
p->rlink->llink=q ；// p 的后继的前驱指向原 p 的前驱
p->rlink=q ；// p 的后继指向其原来的前驱
} //算法 exchange 结束。
（10）已知长度为n的线性表A采用顺序存储结构，请写一个时间复杂度为O(n)、空间复杂度为O(1)的算法，该算法可删除线性表中所有值为item的数据元素。
tips：答案
[ 题目分析 ]在顺序存储的线性表上删除元素，通常要涉及到一系列元素的移动（删第 i 个元素，第 i+1 至第 n 个元素要依次前移） 。本题要求删除线性表中所有值为 item 的数据元素，并未要 求元素间的相对位置不变。因此可以考虑设头尾两个指针（ i=1 ， j=n ），从两端向中间移动， 凡遇到值 item 的数据元素时，直接将右端元素左移至值为 item 的数据元素位置。
[ 算法描述 ]
void Delete (ElemType A[] , int n) // A 是有 n 个元素的一维数组，本算法删除 A 中所有值为 item 的元素。
{
i=1;j=n;//设置数组低、高端指针（下标） 。
while(i
王道习题
tips：答案
hh
有序表. 若线性表中的数据元素相互之间可以比较，并且数据元素在线性表中依值非递减或非递增有序排列，则称该线性表为有序表（Ordered List）。 ↩
插入和删除操作的效率. 对于链表，在确定插入或删除的位置后，插入或删除操作无需移动数据，只需要修改指针，时间复杂度为O(1)。而对于顺序表，进行插入或删除时，平均要移动表中近一半的结点，时间复杂度为O(n)。尤其是当每个结点的信息量较大时，移动结点的时间开销就相当可观。
基于此，对于频繁进行插入或删除操作的线性表，宜采用链表作为存储结构。 ↩
存取元素的效率. 顺序表是由数组实现的，它是一种随机存取结构，指定任意一个位置序号i，都可以在O(1)时间内直接存取该位置上的元素，即取值操作的效率高；而链表是一种顺序存取结构，按位置访问链表中第i个元素时，只能从表头开始依次向后遍历链表，直到找到第i个位置上的元素，时间复杂度为O(n)，即取值操作的效率低。
基于此，若线性表的主要操作是和元素位置紧密相关的这类取值操作，很少做插入或删除时，宜采用顺序表作为存储结构。 ↩
存储密度的大小. 链表的每个结点除了设置数据域用来存储数据元素外，还要额外设置指针域，用来存储指示元素之间逻辑关系的指针，从存储密度上来讲，这是不经济的。所谓存储密度是指数据元素本身所占用的存储量和整个结点结构所占用的存储量之比，即存储密度越大，存储空间的利用率就越高。显然，顺序表的存储密度为1，而链表的存储密度小于1。如果每个元素数据域占据的空间较小，则指针的结构性开销就占用了整个结点的大部分空间，这样存储密度较小。例如，若单链表的结点数据均为整数，指针所占用的空间和整型量相同，则单链表的存储密度为0.5。因此，如果不考虑顺序表中的空闲区，则顺序表的存储空间利用率为100%，而单链表的存储空间利用率仅为50%。
基于此，当线性表的长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表作为存储结构。 ↩
存储空间的分配. 顺序表的存储空间必须预先分配，元素个数扩充受一定限制，易造成存储空间浪费或空间溢出现象；而链表不需要为其预先分配空间，只要内存空间允许，链表中的元素个数就没有限制。
基于此，当线性表的长度变化较大，难以预估存储规模时，宜采用链表作为存储结构。 ↩
顺序表. 特点是表中逻辑上相邻的数据元素，其物理次序也是相邻的。 ↩
特点. 王道
1.表中元素的个数有限
2.表中元素具有逻辑上的顺序性，表中元素有其先后次序
3.表中元素都是数据元素，每个元素都是单个元素
4.表中元素的数据类型都相同，这意味着每个元素占有相同大小的存储空间。
5.表中元素具有抽象性，即仅讨论元素间的逻辑关系，而不考虑元素究竟表示什么内容。
严蔚敏对于非空线性表特点:
1.存在唯一的一个被称为被称为”第一个”的数据元素
2.存在唯一的一个被称为被称为“最后一个”的数据元素
3.除第一个外，结构中的每个数据元素均只有一个前驱
4.除最后一个外，结构中的每个数据元素均只有一个后继 ↩
线性表. 具有相同树类型的n（n>=0）个数据元素的有限序列。(n=0时称为空表) ↩